package P653_两数之和_输入BST;

import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private boolean find(TreeNode root,int k){
        if(root == null){
            return false;
        }
        if(root.val == k){
            return true;
        }else if(root.val < k){
            return find(root.right,k);
        }else{
            return find(root.left, k);
        }
    }
    private boolean fillBucketAndFind(TreeNode root, Map<Integer, Integer> buckets, int k){
        if(buckets.containsKey(root.val)){
            return true;
        }

        buckets.put(k - root.val,1);
        if(root.left != null && fillBucketAndFind(root.left, buckets, k)){
            return true;
        }
        return root.right != null && fillBucketAndFind(root.right, buckets, k);
    }
    public boolean findTarget(TreeNode root, int k) {
        if(root == null){
            return false;
        }
        //TODO 改为hashset更好，只需要看在不在
        Map<Integer,Integer> buckets = new HashMap<>();
        return fillBucketAndFind(root, buckets, k);

//        if(k - root.val > root.val){
//            //看右边的分支情况，以及
//            if(find(root.right,k - root.val)) {
//                return true;
//            }else{
//                return findTarget(root.right,k);
//            }
//        }else{
//            if(find(root.left, k -root.val)) {
//                return true;
//            }else{
//                return findTarget(root.left, k);
//            }
//        }
    }
    public static void main(String args[]){
        TreeNode node1 = new TreeNode(5);
        TreeNode node3 = new TreeNode(3);
        TreeNode node2 = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node1.left = node3;
        node1.right = node6;
        node3.left = node2;
        node3.right = node4;
        node6.left = null;
        node6.right = node7;
        System.out.println(new P653_两数之和_输入BST.Solution().findTarget(node1, 9));
    }
}
